//在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。 
//
// 如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？ 
//
// 例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。 
//
// 给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 
//true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。 
//
// 
//
// 示例 1： 
//
// 
//输入：maxChoosableInteger = 10, desiredTotal = 11
//输出：false
//解释：
//无论第一个玩家选择哪个整数，他都会失败。
//第一个玩家可以选择从 1 到 10 的整数。
//如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
//第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
//同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
// 
//
// 示例 2: 
//
// 
//输入：maxChoosableInteger = 10, desiredTotal = 0
//输出：true
// 
//
// 示例 3: 
//
// 
//输入：maxChoosableInteger = 10, desiredTotal = 1
//输出：true
// 
//
// 
//
// 提示: 
//
// 
// 1 <= maxChoosableInteger <= 20 
// 0 <= desiredTotal <= 300 
// 
// Related Topics 位运算 记忆化搜索 数学 动态规划 状态压缩 博弈 👍 313 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class _464_CanIWin {
    public static void main(String[] args) {
        Solution solution = new _464_CanIWin().new Solution();
        int maxChoosableInteger = 10;
        int desiredTotal = 40;
        System.out.println(solution.canIWin(maxChoosableInteger, desiredTotal));
    }

    class Solution {
        Map<Integer, Boolean> memory = new HashMap<>();

        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            // 如果所有的数字加起来都不超过desiredTotal的话，那么直接false
            if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;
            //否则的话递归判断，判断先手能不能赢，需要注意的是，先手从0开始
            boolean res = dfs(maxChoosableInteger, 0, desiredTotal, 0);
            return res;
        }


        /**
         * @param maxChoosableInteger 供选择的数
         * @param userNumbers         被选择的数，注意用二进制表示，可能比较难以理解。如0010则表示2已经被选择，0001则表示1已被选择
         * @param desiredTotal        累计整数合需要超过的目标值
         * @param currentTotals       当前累计整数合
         * @return
         */
        private boolean dfs(int maxChoosableInteger, int userNumbers, int desiredTotal, int currentTotals) {
            //如果未曾玩过这种场景，则做下列工作找出这种场景的答案
            if (!memory.containsKey(userNumbers)) {
                boolean res = false;
                //循环遍历选择每个数的情况，如果循环完所有的情况，都赢不了，那么就输了，因此初始res是输
                for (int i = 0; i < maxChoosableInteger; i++) {
                    //若这个数还没被选择，才往下做逻辑，否则进入下一轮循环(注意这里i是从0开始，所以判断的是第i+1个数的情况)
                    if (((userNumbers >> i) & 1) == 0) {
                        //如果选完能直接胜利，那么结果自然为true
                        if (i + 1 + currentTotals >= desiredTotal) {
                            res = true;
                            break;
                        }
                        //否则的话，递归判断，我选完后，对方选完是不是就输了；对方输了，我自然就赢了，有点绕
                        if (!dfs(maxChoosableInteger, userNumbers | (1 << i),
                                desiredTotal, currentTotals + i + 1)) {
                            res = true;
                            break;
                        }
                    }
                }
                //把结果放入记忆化
                memory.put(userNumbers, res);
            }
            return memory.get(userNumbers);
        }
        //对于二进制不熟的同学，以下解释一下这题移位法两个操作：（userNumbers >> i) & 1 ：判断i+1是否已经被访问；
        // userNumbers | (1 << i)：把i+1标记为访问。大家可以草稿纸看一下，很好理解

    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution1 {
        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            if (maxChoosableInteger >= desiredTotal) return true;

            while (desiredTotal > maxChoosableInteger) {
                desiredTotal = desiredTotal - maxChoosableInteger - 1;
            }
            return desiredTotal == 0 ? false : true;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

